package JZ_LC;

import java.util.Arrays;
import java.util.HashMap;

public class T_07_根据前中序遍历来得到二叉树 {
    //普通递归（不推荐，易于理解）
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        if (preorder.length != inorder.length) {
            return null;
        }
        int len = preorder.length;
        TreeNode head = new TreeNode(preorder[0]);
        for (int i = 0; i < len; i++) {
            if (inorder[i] == preorder[0]) {
                int[] pre1 = Arrays.copyOfRange(preorder, 1, i + 1);
                int[] pre2 = Arrays.copyOfRange(preorder, i + 1, len);
                int[] in1 = Arrays.copyOfRange(inorder, 0, i);
                int[] in2 = Arrays.copyOfRange(inorder, i + 1, len);
                head.left = buildTree(pre1, in1);
                head.right = buildTree(pre2, in2);
            }
        }
        return head;
    }

    //推荐写法
    HashMap<Integer, Integer> map = new HashMap<>();
    int[] po;

    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        po = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return recur(0, 0, inorder.length - 1);
    }

    private TreeNode recur(int preRoot, int inLeft, int inRight) {
        if (inLeft > inRight) {
            return null;
        }
        TreeNode root = new TreeNode(po[preRoot]);
        int i = map.get(po[preRoot]);
        root.left = recur(preRoot + 1, inLeft, i - 1);
        //preRoot + (i - inLeft)  + 1
        root.right = recur(preRoot + i - inLeft + 1, i + 1, inRight);
        return root;
    }

    //进阶写法（不懂）
    private int in = 0;
    private int pre = 0;

    public TreeNode buildTree3(int[] preorder, int[] inorder) {
        return build(preorder, inorder, Integer.MIN_VALUE);
    }

    private TreeNode build(int[] preorder, int[] inorder, int stop) {
        if (pre >= preorder.length) {
            return null;
        }
        if (inorder[in] == stop) {
            in++;
            return null;
        }

        TreeNode node = new TreeNode(preorder[pre++]);
        node.left = build(preorder, inorder, node.val);
        node.right = build(preorder, inorder, stop);
        return node;
    }
}
